1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits, and more specifically to a method and apparatus for computing a minimum wirelength position (MWP) for a cell in a cell placement for an integrated circuit chip.
2. Description of the Related Art
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. However, it is expected that the feature size can be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnect wire network or net. A goal of the optimization process is to determine a cell placement such that all of the required interconnects can be made, and the total wirelength and interconnect congestion are minimized.
Prior art methods for achieving this goal comprise generating one or more initial placements, modifying the placements using optimization methodologies including Genetic Algorithm operators such as simulated evolution, or simulated annealing, and comparing the resulting placements using a cost criteria.
A prior art method of minimizing the total wirelength of a net is based on computing a "gravity point" of the pins in the net and moving a selected cell to the gravity point. Typical examples of this method are described in articles entitled "INITIAL PLACEMENT OF GATE ARRAYS USING LEAST-SQUARES METHODS", by J. Banks, 21st Design Automation Conference, 1984, and "Efficient Final Placement Based on Nets-as-points", by X. Zhang et al, 26th ACM/IEEE Design Automation Conference, 1989.
Although the gravity point method is computationally easier to implement than the Steiner tree method, it produces a numerical result consisting of a single point to which a cell is to be relocated. There are often other variables to be considered when determining a new position for a cell, such as the number of interconnects passing through a particular interconnect routing channel. Computation of a single gravity point does not allow these additional variables to be considered when relocating a cell to improve the placement.